#include <stdio.h>

#define MAXSTACK    1024

int c = 1;

void move(int n, char x, char y)
{
    printf("%d. Move disk %d from %c to %c\n", c++, n, x, y);
}

void hanoi_1(int n, char x, char y, char z)
{
    if (n <= 0)
        return;

    if (n == 1)
    {
        move(1, x, z);
        return ;
    }

    hanoi_1(n-1, x, z, y);
    move(n, x, z);
    hanoi_1(n-1, y, x, z);
}

void hanoi_2(int n, char x, char y, char z)
{   
    int top, tmp;
    struct step
    {
        int i, l, r;
        char a, b, c;
    } p[MAXSTACK];

    top = 0;
    p[0].i = n; p[0].l = 1; p[0].r = 1; 
    p[0].a = x; p[0].b = y; p[0].c = z;
    while (top >= 0)
    {
        if (p[top].l == 1)
        {
            p[top].l = 0;

            p[top+1].i = p[top].i-1;
            p[top+1].a = p[top].a;
            p[top+1].b = p[top].c;
            p[top+1].c = p[top].b;
            top ++;
            if (p[top].i > 1)
            {
                p[top].l = 1; 
                p[top].r = 1; 
            }
            else
            {
                p[top].l = 0; 
                p[top].r = 0; 
            }
        }
        else
        {
            move(p[top].i, p[top].a, p[top].c);
            
            if (p[top].r == 1)
            {
                p[top].i = p[top].i-1;
                tmp = p[top].a;
                p[top].a = p[top].b;
                p[top].b = tmp;
                if (p[top].i > 1)
                {
                    p[top].l = 1; 
                    p[top].r = 1; 
                }
                else
                {
                    p[top].l = 0; 
                    p[top].r = 0; 
                }
            }
            else
                top --;
        }
    }
}

int main(int argc, char const* argv[])
{
    hanoi_1(4, 'x', 'y', 'z');
    printf("\n");
    c = 1;
    hanoi_2(4, 'x', 'y', 'z');

    return 0;
}
